//
// Created by lenovo on 2023/12/17.
//

#ifndef SORT_QUICKSORT_H
#define SORT_QUICKSORT_H
#include <algorithm>
#include <vector>
#include <string>
using namespace std ;

template <typename T>
int medianThree(vector<T>& src , int left , int mid , int right ){
    if ((src[left] < src[mid]) ^ (src[left]) < src[right])
        return left;
    else if ((src[right] < src[mid]) ^ (src[right] < src[left]))
        return right ;
    else
        return mid ;
}


template <typename T>
int partition(vector<T>&src , int left , int right){
    if (left == right){
        return left ;
    }
    if (left + 1 == right){
        //两个元素的情况我的算法无法正确运行
        //这里直接if-else解决算了
        if (src[left] < src[right]){
            return left ;
        }else{
            swap(src[left] , src[right]);
            return right ;
        }
    }

//    int pivot = medianThree(src , left , (left + right)/2 , right) ;
    int pivot = left ;
    T med = src[pivot];
    int i = left , j = right ;
    while (i < j){
        //要等于的原因
        //防止 i 、j停在与pivot重合的位置无法移动
        while (i < j and src[i] <= med){
            i ++ ;
        }
        while (i < j and src[j] >= med){
            j -- ;
        }
        if (i == j)
            break;
        std::swap(src[i] , src[j]);
    }
    int mid_idx ;
    if (pivot < i){
        mid_idx = i - 1;
    }else{
        mid_idx = j ;
    }
    std::swap(src[pivot] ,src[mid_idx] );
    return mid_idx;
}

template <typename T>
void quickSort(vector<T>&src , int left , int right){
    if (left >= right)
        return ;
    while (left < right){
        int pivot = partition(src , left , right);

        if (pivot - left < right - pivot){
            quickSort(src , left , pivot - 1);
            left = pivot + 1 ;
        }else{
            quickSort(src , pivot + 1, right);
            right = pivot - 1 ;
        }
    }

}

#endif //SORT_QUICKSORT_H
